JOI 11本選 B 古本屋(難易度6)
この問題は動的計画法を用いることで解くことができる.
まず, 貪欲的に考えると, 同じジャンルを選ぶならできるだけ買取価格の高いものから選んでいく方が得である. よって, 各ジャンルごとに本をソートしておいて次のようなDPをする.
$ dp_{i,j}:= $ iジャンル目まで見て, 現在$ j冊選んでいるときの合計買取価格の最大値
$ book_{i,j}:=$ iジャンル目の$ j冊目とする.
$ sum_{i,j}:=$ iジャンル目の$ j番目までの本の買取価格の和(累積和配列)
初期化
すべて$ 0
遷移
$ dp_{i+1, j+k} = max(dp_{i+1,j+k}, dp_{i,j}+sum_{i,k}+k*(k-1))(ただし, $ kは$ iジャンル目を何冊とるかという値である)
答え
$ dp_{10,K}となる
この問題はうまく漸化式を作ることができるかがポイントとなる. 貪欲法との組み合わせが大事である.